package com.LeetCode.Tree;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 根据后续遍历重构二叉搜索树
 */
public class rebuidBST {

    public TreeNode rebuildBST(int[] arr, int left , int right){
        if(left > right)
            return null;
        //根节点
        TreeNode root = new TreeNode(arr[right]);

        if(left == right)
            return root;

        int l = left;
        int r = right;
        //找到分割点
        while(l<r){
            int mid = (l+r)>>>1;
            if(arr[mid] < root.val){
                l = mid + 1;
            }else{
                r = mid;
            }
        }

        root.left = rebuildBST(arr, left , l - 1);
        root.right = rebuildBST(arr, l, right - 1);

        return root;

    }

    public List<List<Integer>> outTree(TreeNode root){
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> cur = new ArrayList<>();
            for(int i = 0; i<len; i++){
                TreeNode node = queue.poll();
                cur.add(node.val);
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
            }
            res.add(cur);
        }
        return res;
    }

    @Test
    public void test(){
        int[] arr = {2,4,3,6,8,7,5};
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
//        outTree(node1).forEach(System.out::println);
        outTree(rebuildBST(arr,0,arr.length-1)).forEach(System.out::println);
    }

    @Test
    public void testBin(){
        int[] arr = {2,4,3,6,8,7,5};
        int l = 0;
        int r = arr.length-1;
        int root = 5;
        while(l<r){
            int mid = (l+r)>>>1;
            if(arr[l] < root){
                l = mid;
            }else{
                r = mid-1;
            }
        }
        System.out.println(arr[l]);
    }
}
